ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Abstract syntax tree</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Abstract syntax tree</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For the trees used in linguistics, see <a href="Parse_tree" title="Parse tree">parse tree</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>An <b>abstract syntax tree</b> (<b>AST</b>) is a data structure used in <a href="Computer_science" title="Computer science">computer science</a> to represent the structure of a program or code snippet. It is a <a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">tree</a> representation of the <a href="Abstract_syntax" title="Abstract syntax">abstract syntactic</a> structure of text (often <a href="Source_code" title="Source code">source code</a>) written in a <a href="Formal_language" title="Formal language">formal language</a>. Each node of the tree denotes a construct occurring in the text. It is sometimes called just a <b>syntax tree</b>.

</p><p>The syntax is "abstract" in the sense that it does not represent every detail appearing in the real syntax, but rather just the structural or content-related details. For instance, grouping <a href="Bracket#Parentheses" title="Bracket">parentheses</a> are implicit in the tree structure, so these do not have to be represented as separate nodes. Likewise, a syntactic construct like an if-condition-then statement may be denoted by means of a single node with three branches.

</p><p>This distinguishes abstract syntax trees from concrete syntax trees, traditionally designated <a href="Parse_tree" title="Parse tree">parse trees</a>. Parse trees are typically built by a <a href="Parser" class="mw-redirect" title="Parser">parser</a> during the source code translation and <a href="Compiler" title="Compiler">compiling</a> process. Once built, additional information is added to the AST by means of subsequent processing, e.g., <a href="Semantic_analysis_(compilers)" title="Semantic analysis (compilers)">contextual analysis</a>.

</p><p>Abstract syntax trees are also used in <a href="Program_analysis" title="Program analysis">program analysis</a> and <a href="Program_transformation" title="Program transformation">program transformation</a> systems.

</p>

<div class="mw-heading mw-heading2"><h2 id="Application_in_compilers">Application in compilers</h2></div>

<p>Abstract syntax trees are <a href="Data_structures" class="mw-redirect" title="Data structures">data structures</a> widely used in <a href="Compilers" class="mw-redirect" title="Compilers">compilers</a> to represent the structure of program code. An AST is usually the result of the <a href="Syntax_analysis" class="mw-redirect" title="Syntax analysis">syntax analysis</a> phase of a compiler. It often serves as an intermediate representation of the program through several stages that the compiler requires, and has a strong impact on the final output of the compiler.

</p>

<div class="mw-heading mw-heading3"><h3 id="Motivation">Motivation</h3></div>

<p>An AST has several properties that aid the further steps of the compilation process:

</p>

<ul><li>An AST can be edited and enhanced with information such as properties and annotations for every element it contains. Such editing and annotation is impossible with the source code of a program, since it would imply changing it.</li>

<li>Compared to the <a href="Source_code" title="Source code">source code</a>, an AST does not include inessential punctuation and delimiters (braces, semicolons, parentheses, etc.).</li>

<li>An AST usually contains extra information about the program, due to the consecutive stages of analysis by the compiler. For example, it may store the position of each element in the source code, allowing the compiler to print useful error messages.</li></ul>

<p>Languages are often <a href="Syntactic_ambiguity" title="Syntactic ambiguity">ambiguous</a> by nature. In order to avoid this ambiguity, programming languages are often specified as a <a href="Context-free_grammar" title="Context-free grammar">context-free grammar</a> (CFG). However, there are often aspects of programming languages that a CFG can't express, but are part of the language and are documented in its specification. These are details that require a context to determine their validity and behaviour. For example, if a language allows new types to be declared, a CFG cannot predict the names of such types nor the way in which they should be used. Even if a language has a predefined set of types, enforcing proper usage usually requires some context. Another example is <a href="Duck_typing" title="Duck typing">duck typing</a>, where the type of an element can change depending on context. <a href="Operator_overloading" title="Operator overloading">Operator overloading</a> is yet another case where correct usage and final function are context-dependent.

</p>

<div class="mw-heading mw-heading3"><h3 id="Design">Design</h3></div>

<p>The design of an AST is often closely linked with the design of a compiler and its expected features.

</p><p>Core requirements include the following:

</p>

<ul><li>Variable types must be preserved, as well as the location of each declaration in source code.</li>

<li>The order of executable statements must be explicitly represented and well defined.</li>

<li>Left and right components of binary operations must be stored and correctly identified.</li>

<li>Identifiers and their assigned values must be stored for assignment statements.</li></ul>

<p>These requirements can be used to design the data structure for the AST.

</p><p>Some operations will always require two elements, such as the two terms for addition. However, some language constructs require an arbitrarily large number of children, such as argument lists passed to programs from the <a href="Command_shell" class="mw-redirect" title="Command shell">command shell</a>. As a result, an AST used to represent code written in such a language has to also be flexible enough to allow for quick addition of an unknown quantity of children.

</p><p>To support compiler verification it should be possible to unparse an AST into source code form. The source code produced should be sufficiently similar to the original in appearance and identical in execution, upon recompilation.

The AST is used intensively during <a href="Semantic_analysis_(compilers)" title="Semantic analysis (compilers)">semantic analysis</a>, where the compiler checks for correct usage of the elements of the program and the language. The compiler also generates <a href="Symbol_table" title="Symbol table">symbol tables</a> based on the AST during semantic analysis. A complete traversal of the tree allows verification of the correctness of the program.

</p><p>After verifying correctness, the AST serves as the base for code generation. The AST is often used to generate an intermediate representation (IR), sometimes called an <a href="Intermediate_language" class="mw-redirect" title="Intermediate language">intermediate language</a>, for the code generation.

</p>

<div class="mw-heading mw-heading2"><h2 id="Other_usages">Other usages</h2></div>

<div class="mw-heading mw-heading3"><h3 id="AST_differencing">AST differencing</h3></div>

<p>AST differencing, or for short tree differencing, consists of computing the list of differences between two ASTs.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> This list of differences is typically called an edit script. The edit script directly refers to the AST of the code. For instance, an edit action may result in the addition of a new AST node representing a function.

</p>

<div class="mw-heading mw-heading3"><h3 id="Clone_detection">Clone detection</h3></div>

<p>An AST is a powerful abstraction to perform code <a href="Clone_detection" class="mw-redirect" title="Clone detection">clone detection</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Abstract_semantic_graph" title="Abstract semantic graph">Abstract semantic graph</a> (ASG), also called <i>term graph</i></li>

<li><a href="Composite_pattern" title="Composite pattern">Composite pattern</a></li>

<li><a href="Control-flow_graph" title="Control-flow graph">Control-flow graph</a></li>

<li><a href="Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a> (DAG)</li>

<li><a href="Document_Object_Model" title="Document Object Model">Document Object Model</a> (DOM)</li>

<li><a href="Expression_tree" class="mw-redirect" title="Expression tree">Expression tree</a></li>

<li><a href="Extended_Backus%E2%80%93Naur_form" title="Extended Backus–Naur form">Extended Backus–Naur form</a></li>

<li><a href="Lisp_(programming_language)" title="Lisp (programming language)">Lisp</a>, a family of languages written in trees, with macros to manipulate code trees</li>

<li><a href="Parse_tree" title="Parse tree">Parse tree</a>, also known as <i>concrete syntax tree</i></li>

<li><a href="Semantic_resolution_tree" title="Semantic resolution tree">Semantic resolution tree</a> (SRT)</li>

<li><a href="Shunting-yard_algorithm" class="mw-redirect" title="Shunting-yard algorithm">Shunting-yard algorithm</a></li>

<li><a href="Symbol_table" title="Symbol table">Symbol table</a></li>

<li><a href="TreeDL" title="TreeDL">TreeDL</a></li>

<li><a href="Interpreter_(computing)#Abstract_syntax_tree_interpreters" title="Interpreter (computing)">Abstract Syntax Tree Interpreters</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFFluriWurschPInzgerGall2007" class="citation journal cs1">Fluri, Beat; Wursch, Michael; PInzger, Martin; Gall, Harald (2007). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://dx.doi.org/10.1109/tse.2007.70731">"Change Distilling:Tree Differencing for Fine-Grained Source Code Change Extraction"</a></span>. <i>IEEE Transactions on Software Engineering</i>. <b>33</b> (11): <span class="nowrap">725–</span>743. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftse.2007.70731">10.1109/tse.2007.70731</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0098-5589">0098-5589</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13659557">13659557</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFKoschkeFalkeFrenzel2006" class="citation book cs1">Koschke, Rainer; Falke, Raimar; Frenzel, Pierre (2006). <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1109/wcre.2006.18">"Clone Detection Using Abstract Syntax Suffix Trees"</a>. <i>2006 13th Working Conference on Reverse Engineering</i>. IEEE. pp. <span class="nowrap">253–</span>262. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Fwcre.2006.18">10.1109/wcre.2006.18</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7695-2719-1</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6985484">6985484</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFJones" class="citation web cs1">Jones, Joel. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20240721094334/http://hillside.net/plop/plop2003/Papers/Jones-ImplementingASTs.pdf">"Abstract Syntax Tree Implementation Idioms"</a> <span class="cs1-format">(PDF)</span>. Archived from <a rel="nofollow" class="external text" href="http://www.hillside.net/plop/plop2003/Papers/Jones-ImplementingASTs.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 21 July 2024<span class="reference-accessdate">. Retrieved <span class="nowrap">9 November</span> 2011</span>.</cite> (overview of AST implementation in various language families)</li>

<li><cite id="CITEREFNeamtiuFosterHicks2005" class="citation conference cs1">Neamtiu, Iulian; Foster, Jeffrey S.; Hicks, Michael (May 17, 2005). <i>Understanding Source Code Evolution Using Abstract Syntax Tree Matching</i>. MSR'05. Saint Louis, Missouri: ACM. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.88.5815">10.1.1.88.5815</a></span>.</cite></li>

<li><cite id="CITEREFWürsch" class="citation thesis cs1">Würsch, Michael. <a rel="nofollow" class="external text" href="http://www.ifi.uzh.ch/seal/research/tools/archive/changeDetection.html"><i>Improving Abstract Syntax Tree based Source Code Change Detection</i></a> (Diploma thesis).</cite></li>

<li><cite id="CITEREFLucas2006" class="citation web cs1">Lucas, Jason (16 August 2006). <a rel="nofollow" class="external text" href="https://devblogs.microsoft.com/cppblog/thoughts-on-the-visual-c-abstract-syntax-tree-ast/">"Thoughts on the Visual C++ Abstract Syntax Tree (AST)"</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Abstract_syntax_trees" class="extiw external" title="commons:Category:Abstract syntax trees">Abstract syntax trees</a></span>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="http://www.eclipse.org/jdt/ui/astview/index.php">AST View</a>: an <a href="Eclipse_(software)" title="Eclipse (software)">Eclipse</a> plugin to <a href="Scientific_visualization" title="Scientific visualization">visualize</a> a <a href="Java_(programming_language)" title="Java (programming language)">Java</a> abstract syntax tree</li>

<li><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.eclipse.org/articles/Article-JavaCodeManipulation_AST/index.html">"Abstract Syntax Tree and Java Code Manipulation in the Eclipse IDE"</a>. <i>eclipse.org</i>.</cite></li>

<li><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.cs.utah.edu/flux/flick/current/doc/guts/gutsch6.html">"CAST representation"</a>. <i>cs.utah.edu</i>.</cite></li>

<li><a rel="nofollow" class="external text" href="https://eli-project.sourceforge.net/elionline/idem_3.html">eli project</a>: Abstract Syntax Tree <a href="Unparsing" class="mw-redirect" title="Unparsing">Unparsing</a></li>

<li><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.omg.org/spec/ASTM/">"Architecture‑Driven Modernization — ADM: Abstract Syntax Tree Metamodeling — ASTM"</a>.</cite> (<a href="Object_Management_Group" title="Object Management Group">OMG</a> standard).</li>

<li><a rel="nofollow" class="external text" href="https://javaparser.org">JavaParser</a>: The JavaParser library provides you with an Abstract Syntax Tree of your Java code. The AST structure then allows you to work with your Java code in an easy programmatic way.</li>

<li><a rel="nofollow" class="external text" href="https://github.com/INRIA/spoon">Spoon</a>: A library to analyze, transform, rewrite, and transpile Java source code. It parses source files to build a well-designed AST with powerful analysis and transformation API.</li>

<li><a rel="nofollow" class="external text" href="https://astexplorer.net">AST Explorer</a>: A website to help visualize ASTs in several popular languages such as Go, Python, Java, and JavaScript.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Parsing_algorithms116" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Parsing_algorithms116" style="font-size:114%;margin:0 4em"><a href="Parsing" title="Parsing">Parsing algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Top-down_parsing" title="Top-down parsing">Top-down</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Earley_parser" title="Earley parser">Earley</a></li>

<li><a href="Recursive_descent_parser" title="Recursive descent parser">Recursive descent</a>

<ul><li><a href="Tail_recursive_parser" title="Tail recursive parser">Tail recursive</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Bottom-up_parsing" title="Bottom-up parsing">Bottom-up</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Precedence

<ul><li><a href="Simple_precedence_parser" title="Simple precedence parser">Simple</a></li>

<li><a href="Operator-precedence_parser" title="Operator-precedence parser">Operator</a>

<ul><li><a href="Shunting_yard_algorithm" title="Shunting yard algorithm">Shunting-yard</a></li></ul></li></ul></li>

<ul><li><a href="Simple_LR_parser" title="Simple LR parser">Simple</a></li>

<li><a href="LALR_parser" title="LALR parser">Look-ahead</a></li>

<li><a href="Canonical_LR_parser" title="Canonical LR parser">Canonical</a></li>

<li><a href="GLR_parser" title="GLR parser">Generalized</a></li></ul></li>

<li><a href="Recursive_ascent_parser" title="Recursive ascent parser">Recursive ascent</a></li>

<li><a href="Shift-reduce_parser" title="Shift-reduce parser">Shift-reduce</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Mixed, other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parser_combinator" title="Parser combinator">Combinator</a></li>

<li><a href="Chart_parser" title="Chart parser">Chart</a>

<ul><li><a href="Left_corner_parser" title="Left corner parser">Left corner</a></li></ul></li>

<li>Statistical</li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related topics</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Definite_clause_grammar" title="Definite clause grammar">Definite clause grammar</a></li>

<li><a href="Deterministic_parsing" title="Deterministic parsing">Deterministic parsing</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Memoization" title="Memoization">Memoization</a></li>

<li><a href="Compiler-compiler" title="Compiler-compiler">Parser generator</a>

<li><a href="Parse_tree" title="Parse tree">Parse tree</a></li>

<li><a href="Scannerless_parsing" title="Scannerless parsing">Scannerless parsing</a></li>

<li><a href="History_of_compiler_construction" title="History of compiler construction">History of compiler construction</a></li>

<li><a href="Comparison_of_parser_generators" title="Comparison of parser generators">Comparison of parser generators</a></li>

<li><a href="Operator-precedence_grammar" title="Operator-precedence grammar">Operator-precedence grammar</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox390" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Authority control databases: National </th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4702177-9">Germany</a></span></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-06" href="https://en.wikipedia.org/wiki/?title=Abstract_syntax_tree&oldid=1304512722">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>